/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * @author zhongfang
 *
 */
public class AccountsMerge {
	class Person {
		String name;
		List<Email> emails;

		public Person(List<String> list) {
			name = list.get(0);
			for (int i = 1; i < list.size(); i++) {
				Email mEmail = new Email(this, list.get(i));
				emails.add(mEmail);
			}
		}
	}

	class Email {
		public Email(Person person2, String string) {
			this.person = person2;
			this.mail = string;
		}

		String mail;
		Person person;
	}

	/*
	 * 超时
	 */
	public List<List<String>> accountsMerge(List<List<String>> accounts) {
		HashMap<String, List<List<String>>> name2Emial = new HashMap<>();
		for (List<String> curPerson : accounts) {
			String name = curPerson.get(0);
			curPerson.remove(0);
			// 先对内部去重
			List<String> after = new ArrayList<>(curPerson.size());
			Set<String> set = new HashSet<>(curPerson.size());
			for (int i = 0; i < curPerson.size(); i++) {
				if (set.add(curPerson.get(i))) {
					after.add(curPerson.get(i));
				}
			}
			curPerson = after;
			Collections.sort(curPerson);
			boolean combineTag = false;
			List<List<String>> samePerson = new ArrayList<>();// 可能有多个相同的人
			if (name2Emial.containsKey(name)) {
				List<List<String>> allPers = name2Emial.get(name);
				for (int j = 0; j < curPerson.size(); j++) {// 这个email
					String curEmial = curPerson.get(j);
					for (int i = 0; i < allPers.size(); i++) {// 其他已有用户
						List<String> person = allPers.get(i);
						int index = Collections.binarySearch(person, curEmial);
						if (index >= 0) {// 同名用户包含这个邮箱
							combineTag = true;
							samePerson.add(person);
							break;
						}
					}
				}

				if (combineTag) {
					// 当前用户的所有邮箱加入以前这个用户，并且按顺序
					samePerson.add(curPerson);
					List<String> targetP = combinePerson(samePerson);
					// 移除除了第一个之外的所有元素
					allPers.removeAll(samePerson);
					allPers.add(targetP);
				} else {
					name2Emial.get(name).add(curPerson);
				}
			} else {
				// 放入map
				List<List<String>> pLists = new ArrayList<>();
				pLists.add(curPerson);
				name2Emial.put(name, pLists);
			}
		}

		List<List<String>> res = new ArrayList<>();
		for (Map.Entry<String, List<List<String>>> entry : name2Emial.entrySet()) {
			List<List<String>> list = entry.getValue();
			String name = entry.getKey();
			for (int i = 0; i < list.size(); i++) {
				list.get(i).add(0, name);
			}
			res.addAll(list);
		}
		return res;
	}

	private List<String> combinePerson(List<List<String>> samePerson) {
		List<String> targetP = samePerson.get(0);
		for (int j = 1; j < samePerson.size(); j++) {
			List<String> curPerson = samePerson.get(j);
			for (int i = 0; i < curPerson.size(); i++) {
				String curEmial = curPerson.get(i);
				int index = Collections.binarySearch(targetP, curEmial);
				if (index < 0) {
					index = -index - 1;
					// 插入到当前位置
					targetP.add(index, curEmial);
				}
			}
		}
		return targetP;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[][] accounts = { { "John", "johnsmith@mail.com", "john00@mail.com", "john00@mail.com" },
				{ "John", "johnnybravo@mail.com", "johnnybravo@mail.com" },
				{ "John", "johnsmith@mail.com", "johnsmith@mail.com", "john_newyork@mail.com",
						"john_newyork@mail.com" },
				{ "Mary", "mary@mail.com", "mary@mail.com" }, { "John", "john00@mail.com", "johnnybravo@mail.com" } };
		List<List<String>> acc = arr2Lis(accounts);
		System.out.println(new AccountsMerge().accountsMergeACC(acc));
	}

	class Account {
		String name;
		List<String> emails;

		@Override
		public String toString() {
			return "name: " + this.name + "  email:" + emails.toString();
		}

		public Account(List<String> list) {
			name = list.get(0);
			emails = list.subList(1, list.size());
			Collections.sort(emails);// 对于单个的列表（不会和其他账户合并的）也要注意去重
			ArrayList<String> res = new ArrayList<>(emails.size());
			String prev = "";
			for (String string : emails) {
				if (!string.equals(prev)) {
					res.add(string);
					prev = string;
				}
			}
			this.emails = res;
		}

		class Node {
			String val;
			int index;// 第几个数组
			int j;// 数组里的下标

			@Override
			public boolean equals(Object obj) {
				Node node = (Node) obj;
				return val.equals(node.val);
			}

			@Override
			public int hashCode() {
				return val.hashCode();
			}

			public Node(String val, int index) {
				this.val = val;
				this.index = index;
				this.j = 0;
			}
		}

		public ArrayList<String> mergeEmail(List<Account> list) {
			ArrayList<String> reStrings = new ArrayList<>();
			PriorityQueue<Node> queue = new PriorityQueue<>();

			for (int i = 0; i < list.size(); i++) {
				queue.add(new Node(list.get(i).emails.get(0), i));
			}
			while (!queue.isEmpty()) {
				// 从队列中取出一个最小的
				Node node = queue.poll();
				reStrings.add(node.val);
				// 放入下一个元素
				node.j++;
				node.val = list.get(node.index).emails.get(node.j);
				queue.add(node);
			}
			return reStrings;
		}

		/**
		 * 归并排序
		 * 
		 * @param neib
		 */
		public void mergeEmail(Account neib) {
			int i = 0, j = 0;
			int size1 = this.emails.size();
			int size2 = neib.emails.size();
			String cur = "";
			ArrayList<String> reStrings = new ArrayList<>(size1 + size2);
			while (i < size1 && j < size2) {
				int c = this.emails.get(i).compareTo(neib.emails.get(j));
				if (c < 0) {
					cur = this.emails.get(i++);
				} else if (c > 0) {
					cur = neib.emails.get(j++);
				} else {
					cur = neib.emails.get(j++);
					i++;
				}
				reStrings.add(cur);
			}
			while (i < size1) {
				cur = this.emails.get(i++);
				reStrings.add(cur);
			}
			while (j < size2) {
				cur = neib.emails.get(j++);
				reStrings.add(cur);
			}
			this.emails = reStrings;
		}
	}

	/**
	 * BFS+set 超时
	 * 
	 * @param acc
	 * @return
	 */
	public List<List<String>> accountsMergeACC(List<List<String>> acc) {
		HashMap<String, List<Account>> accountsSameName = new HashMap<>();// 同一个名字下的多个不同账户
		HashMap<Account, List<Account>> sameAccEdges = new HashMap<>();// 直接相同（同名且有一个同email）的账户，建立一个边的关系
		// 对于每个人一个节点，里面是排序的邮箱，合并人的操作是
		for (List<String> list : acc) {
			String name = list.get(0);
			Account cur = new Account(list);
			if (accountsSameName.containsKey(name)) {
				List<Account> sames = new ArrayList<>();// 同名且有相同邮箱的相同账号列表
				for (Account accountSameName : accountsSameName.get(name)) {// 所有同名账户
					for (String email : cur.emails) {
						int index = Collections.binarySearch(accountSameName.emails, email);
						if (index >= 0) {
							sames.add(accountSameName);
							break;
						}
					}
				}
				accountsSameName.get(name).add(cur);// 加入同名集合
				if (sames.isEmpty()) {// 不存在same的账号
					sameAccEdges.put(cur, new ArrayList<>());// 加入节点
				} else {// 建立边的联系
					sameAccEdges.put(cur, sames);
					// sames有多个，注意合并
					for (Account account : sames) {
						sameAccEdges.get(account).add(cur);
					}
				}
			} else {// 不存在同名的账户
				ArrayList<Account> list2 = new ArrayList<>();
				list2.add(cur);
				accountsSameName.put(name, list2);// 加入同名集合

				sameAccEdges.put(cur, new ArrayList<>());// 节点
			}
		}
		// 利用BFS/DFS合并相同账户
		List<List<String>> res = new ArrayList<>();
		List<Account> reAccounts = new ArrayList<>();// 所有起始的账户

		HashSet<Account> visited = new HashSet<>();
		for (Account account : sameAccEdges.keySet()) {
			if (!visited.add(account))// 跳过已经访问过的
				continue;
			reAccounts.add(account);// 起始点
			Queue<Account> queue = new LinkedList<>();
			queue.add(account);
			while (!queue.isEmpty()) {// BFS把等价的账户合并
				Account cur = queue.poll();
				for (Account neib : sameAccEdges.get(cur)) {// 相邻点
					if (visited.add(neib)) {
						queue.add(neib);
						// 把它合并到起始点的account的emial里面
						account.mergeEmail(neib);
					}
				}
			}
		}
		// 得到结果的过程中【不需要去重，因为合并过程中把=给去掉了】
		for (Account account : reAccounts) {
			ArrayList<String> list = new ArrayList<>();
			list.add(account.name);
			list.addAll(account.emails);
			res.add(list);
		}
		return res;
	}

	private static List<List<String>> arr2Lis(String[][] accounts) {
		List<List<String>> res = new ArrayList<>(accounts.length);
		for (int i = 0; i < accounts.length; i++) {
			List<String> tmp = new ArrayList<>(accounts[i].length);
			for (int j = 0; j < accounts[i].length; j++) {
				tmp.add(accounts[i][j]);
			}
			res.add(tmp);
		}
		return res;
	}

}
